package com.guaoran.algorithm.two.pointer;

import java.util.Arrays;

/**
 * @Auth gucheng
 * @Desc 验证三角形
 * https://leetcode.com/problems/valid-triangle-number/
 * @Date 2021/1/15 上午10:56
 */
public class ValidTriangleNumber {
    public static void main(String[] args) {
        int[] nums = {2,2,3,4};
        System.out.println(triangleNumber(nums));
    }

    private static int triangleNumber(int[] nums) {
        if(nums == null || nums.length < 3){
            return 0;
        }
        Arrays.sort(nums);
        int count = 0;
        for (int i = nums.length -1; i>=2;i--){
            int start= 0;
            int end = i -1;
            while(start<end){
                if(nums[start] + nums[end] > nums[i]){
                    // 如果最小的 start 所在一边 + 一边 > 另一边
                    // 则 start + 1 也会满足的
                    // 所以这里直接用下标 end - start，获取start 所有满足的数量
                    count += (end -start);
                    end --;
                }else {
                    start ++;
                }
            }
        }
        return count;
    }
}
